package class03

/*
	给定一个由字符串组成的数组，给定一个正数K
	返回词频最大的前K个字符串，假设结果是唯一的
*/

type KNode struct {
	key string
	Num int
}

func KNodeCompare(node1, node2 interface{}) bool {
	return node1.(KNode).Num < node2.(KNode).Num
}

func printTopKAndRank(strS []string, topK int) []string {
	frequencyMap := make(map[string]int)
	for _, s := range strS {
		if _, ok := frequencyMap[s]; ok {
			frequencyMap[s]++
		} else {
			frequencyMap[s] = 1
		}
	}
	var ans []string
	if len(frequencyMap) <= topK {
		for key,_ :=range frequencyMap {
			ans = append(ans, key)
		}
		return ans
	}
	mySmallHeap := NewMyHeap(topK, KNodeCompare)
	for key, num := range frequencyMap {
		n := KNode{key, num}
		if mySmallHeap.Size() < topK {
			mySmallHeap.Insert(n)
		} else {
			mostSmall := mySmallHeap.Top().(KNode)
			if mostSmall.Num < n.Num {
				mySmallHeap.Poll()
				mySmallHeap.Insert(n)
			}
		}
	}
	for mySmallHeap.Size() > 0 {
		ans = append(ans, mySmallHeap.Poll().(KNode).key)
	}
	return ans
}



